The present invention relates to a Viterbi decoder that is provided in a receiver and decodes an error-correcting encoded information symbol string in a communication system in which an information symbol string is transmitted after being error-correcting encoded by means of a feedback-type convolutional encoder and being quadrature amplitude-modulated.
In the digital communication field, error-correcting encoding methods and modulation methods have conventionally been considered as separate and independent subjects. Recently however, an encoded modulation technique that combines error-correcting techniques and modulation/demodulation techniques has been proposed (G. Ungerboeck, Channel Coding with Multilevel/Phase Signals, IEEE Transactions on Information Theory, vol. IT-28, January 1983). This proposed encoded modulation technique is a technique of quadrature amplitude-modulating an error-correcting encoded information symbol string which is generated by error-correcting encoding an information symbol string by means of a convolutional encoder, but in the process of quadrature amplitude modulation, a measure has been taken for the arrangement of transmission symbol points. According to this measure, in the convolutional encoder, through the addition of 1-bit redundancy based on the states of finite state memories provided in the convolutional encoder, an N-bit information string is converted to an (N+1)-bit error-correcting encoded information symbol string. The error-correcting encoded information symbol string, when quadrature amplitude-modulated, is mapped onto one of 2.sup.N+1 transmission symbol points. The 2.sup.N+1 transmission symbol points are then arranged in a two-dimensional plane based on an I-axis and a Q-axis. The error-correcting encoded information symbol string is mapped onto one of the two-dimensionally distributed 2.sup.N+1 transmission symbol points in accordance with its value. As described in the above-mentioned reference, the 2.sup.N+1 transmission symbol points are divided into subsets each of which is constituted by two transmission symbol points. The Euclidean distance between the two transmission symbol points belonging to each subset is then made greater than the Euclidean distance between two arbitrary transmission symbol points.
Encoding an information symbol string by a feedback-type convolutional encoder is carried out in the following manner. An N-bit information symbol string is divided into noncoding bits that have no influence on the state transition of the finite state memories of the feedback-type convolutional encoder and influence bits, referred to as IB bits, that have influence on the state transition of the finite memories of the feedback-type convolutional encoder. The IB bits are inputted to the finite state memories of the feedback-type convolutional encoder. As a result, through the addition of a 1-bit redundancy based on the state of the finite state memories, the information symbol string is converted into an (N+1)-bit error-correcting encoded information symbol string. Here, the IB bits and a redundant bit that adds the 1-bit redundancy to the information symbol string are termed "encoding bits."
If the bit number of the noncoding bits is "K," the 2.sup.N+1 transmission symbol points are divided into the 2.sup.K subsets each of which is constituted by two transmission symbol points. In accordance with the state transition of the finite state memories, a subset corresponding to the information symbol string is selected such that only a few sequences are effective. By selecting one transmission symbol point from the two transmission symbol points of the selected subset according to the noncoding bits, the error-correcting encoded information symbol string is mapped onto one of the 2.sup.N+1 transmission symbol points.
The decoding of the error-correcting encoded information symbol string encoded as described above is considered to be possible through the use of a Viterbi algorithm known as a maximum likelihood decoding method. The concrete composition of a Viterbi decoder is described in, for example, Aikawa et al. "The Method of Constructing a Viterbi Decoding Circuit Suitable for High-speed Multi-valued Trellis Encoded Modulation" Journal of the Electronic Information Communication Society, vol. J73-A, No. 2, February 1990. The decoding method of conventional Viterbi decoders is carried out by using a grid graph having a vertical axis representing the state of the feedback-type convolutional encoder and a horizontal axis representing the block number in order to find the encoded sequence which has the shortest hamming distance between the received information symbol string.
An example of the construction of a Viterbi decoder will be described for a case in which is transmitted an error-correcting encoded information symbol string (x.sub.3 x.sub.2 x.sub.1 x.sub.0) made up from a 3-bit information symbol string (x.sub.3 x.sub.2 x.sub.1) and a 1-bit redundant bit x.sub.0. In addition, the two higher-order bits within information symbol string (x.sub.3 x.sub.2 x.sub.1) are noncoding bits x.sub.3 x.sub.2 that do not influence the state transition of the finite state memories of the feedback-type convolutional encoder, and the lowest-order bit is IB bit x.sub.1 that has influence on the state transition of the finite state memories of the feedback-type convolutional encoder. IB bit x.sub.1 and redundant bit x.sub.0 are termed encoding bits x.sub.1 x.sub.0. In addition, the feedback-type convolutional encoder has three finite state memories. In other words, the feedback-type convolutional encoder has 2.sup.3 =8 states. The number of subsets is 2.sup.2 =4 (hereinafter referred to as subsets A, B, C, and D) and the number of transmission symbol points is 2.sup.4.
A Viterbi decoder 30 shown in FIG. 1 includes an inverse mapping circuit 33, first to fourth branch metric generators 34.sub.1 -34.sub.4, first to eighth accumulator switch circuits (hereinafter referred to as ACS circuits 35.sub.1 -35.sub.8), of which one circuit corresponds to one of the eight states of the feedback-type convolutional encoder, a path memory 36, a re-encoder 37, first to fourth shift registers 38.sub.1 -38.sub.4 having a number of levels set with consideration taken for the delay in the re-encoder 37 and the delay in the path memory 36, and a selector 39. The transmitted signal sent from a transmitter to a receiver is converted to two demodulated signals by means of orthogonal synchronous detection carried out by a orthogonal synchronous detector (not shown) of the receiver. Each of the two demodulated signals is converted to m-bit I-channel data Ich and m-bit Q-channel data Qch by the quantization of their amplitude values by a quantizing circuit (not shown). Here, I-channel data Ich and Q-channel data Qch are 2m-value soft decision data. I-channel data Ich and Q-channel data Qch are both inputted to the inverse mapping circuit 33 by way of two input terminals 31, 32. In the inverse mapping circuit 33, the representative symbol points of subsets A, B, C, and D are found from I-channel data Ich and Q-channel data Qch. Each of the found representative symbol points of subsets A, B, C, and D is inverse mapped onto 4-bit data corresponding to it. The noncoding bits which are the two higher-order bits of the 4-bit data inverse mapped for subset A are inputted to the first shift register 38.sub.1. The noncoding bits which are the two higher-order bits of the 4-bit data inverse mapped for subset B are inputted to the second shift register 38.sub.2. The noncoding bits which are the two higher-order bits of the 4-bit data inverse mapped for subset C are inputted to the third shift register 38.sub.3. The noncoding bits which are the two higher-order bits of the 4-bit data inverse mapped for subset D are inputted to the fourth shift register 38.sub.4.
In the first branch metric generator 34.sub.1, a branch metric is calculated based on the Euclidean distance between the representative symbol point of subset A found in the inverse mapping circuit 33 and a reception symbol point indicated by I-channel data Ich and Q-channel data Qch. In the second branch metric generator 34.sub.2, a branch metric is calculated based on the Euclidean distance between the representative symbol point of subset B found in the inverse mapping circuit 33 and the reception symbol point. In the third branch metric generator 34.sub.3, a branch metric is calculated based on the Euclidean distance between the representative symbol point of subset C found in the inverse mapping circuit 33 and the reception symbol point. In the fourth branch metric generator 34.sub.4, a branch metric is calculated based on the Euclidean distance between the representative symbol point of subset D found in the inverse mapping circuit 33 and the reception symbol point. The branch metric calculated in the first branch metric generator 34.sub.1 is inputted to the first ACS circuit 35.sub.1, the third ACS circuit 35.sub.3, the fifth ACS circuit 35.sub.5, and the seventh ACS circuit 35.sub.7. The branch metric calculated in the second branch metric generator 34.sub.2 is inputted to the second ACS circuit 35.sub.2, the fourth ACS circuit 35.sub.4, the sixth ACS circuit 35.sub.6, and the eighth ACS circuit 35.sub.8. The branch metric calculated in the third branch metric generator 34.sub.3 is inputted to the second ACS circuit-35.sub.2, the fourth ACS circuit 35.sub.4, the sixth ACS circuit 35.sub.6, and the eighth ACS circuit 35.sub.8. The branch metric calculated in the fourth branch metric generator 34.sub.4 is inputted to the first ACS circuit 35.sub.1, the third ACS circuit 35.sub.3, the fifth ACS circuit 35.sub.5, and the seventh ACS circuit 35.sub.7.
In each ACS circuit 35.sub.1 -35.sub.8, in accordance with the two inputted branch metrics and all of the state transitions prescribed by the feedback-type convolutional encoder, each of the path metric accumulated values which are held by the several states combined in transition with one state among eight states S.sub.0 -S.sub.7 of the feedback-type convolutional encoder is added to the predetermined one of the two inputted branch metrics, and the greatest addition value is selected as the new path metric of the one state. The eight path metrics calculated in ACS circuits 35.sub.1 -35.sub.8 are inputted to the path memory 36, and decoded data is obtained in the path memory 36 by sequentially updating its contents according to the inputted path metrics. However, the decoded data obtained in the path memory 36 is only IB bit x.sub.1 of encoding bits x.sub.1 x.sub.0 and not encoding bits x.sub.1 x.sub.0 of 4-bit error-correcting encoded information symbol string (x.sub.3 x.sub.2 x.sub.1 x.sub.0). IB bit x.sub.1 obtained in the path memory 36 is inputted to the re-encoder 37, and in the re-encoder 37, the encoding bits x.sub.1 x.sub.0 are calculated based on IB bit x.sub.1. Here, encoding bits x.sub.1 x.sub.0 calculated in the re-encoder 37 represent one of four subsets A, B, C, and D. Encoding bits x.sub.1 x.sub.0 calculated in the re-encoder 37 are inputted to the selector 39. In the selector 39, the noncoding bits x.sub.3 x.sub.2 of 4-bit error-correcting encoded information symbol string (x.sub.3 x.sub.2 x.sub.1 x.sub.0) are decoded by selecting from the output signals of first to fourth shift-registers 38.sub.1 -38.sub.4 the output signal that corresponds to the subset represented by encoding bits x.sub.1 x.sub.0 calculated in the re-encoder 37. IB bit x.sub.1 obtained with the path memory 36 and noncoding bits x.sub.3 x.sub.2 selected in the selector 39 are outputted as the decoded data of information-symbol string (x.sub.3 x.sub.2 x.sub.1) to the outside from an output terminal 40 and an output terminal 41.
In the Viterbi decoder 30 shown in FIG. 1 with fixed and unchanging structure of the decoder and the bit number n of I-channel data Ich and Q-channel data Qch, in cases where an information symbol string is multi-valued in order to send a large volume of information bits, redundancy begins to be sent to the first through fourth shift registers 38.sub.1 -38.sub.4 when the bit number of I-channel data Ich and Q-Channel data Qch corresponding to bit number L of the noncoding bits and bit number K of the encoding bits satisfies the relation: EQU n&lt;L.times.2.sup.K-2
Consequently, the application of Large-Scale Integrated Circuit (LSI) to the Viterbi decoder 30 results in the use of superfluous gates. For example, when the bit number of the encoding bits is K=2 and the bit number of I-channel data Ich and Q-channel data Qch is n=5 (a soft decision value of 32), bit number L of the noncoding bits is greater than 2.5. In other words, when bit number L of the noncoding bits is greater than 3, the application of LSI to the first through fourth shift registers 38.sub.1 -38.sub.4 results in the use of superfluous shift gates.